/**
 * @author ChaP
 * @date 2019/05/24
 * @describe:
 */
package CodingTest.AC20190524;

/**leetcode - 459
 * 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

 示例 1:

 输入: "abab"

 输出: True

 解释: 可由子字符串 "ab" 重复两次构成。
 示例 2:

 输入: "aba"

 输出: False
 示例 3:

 输入: "abcabcabcabc"

 输出: True

 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 */
public class repeatedSubstringPattern {
    //方法一：
    public boolean repeatedSubstringPattern(String s){
        int i =1,j=0,n=s.length();
        int[] dp = new int[n+1];
        while(i<n){
            if(s.charAt(i) == s.charAt(j)){
                dp[++i] = ++j;
            }else if(j == 0){ i++;}
            else{j = dp[j];}
        }

        boolean a = (n%(n-dp[n])==0);
        return dp[n]>0 && a;
    }

    //方法二：
    public boolean repeatedSubstringPattern1(String s){
        int len = s.length();
        for(int i = 1;i<=len/2;i++){
            String sonStr =getSonStr(i,s);
            boolean res = isSonString(s,sonStr);
            if(res == true) return true;
        }
        return false;
    }
    //这里使用stringBuffer就超时
    public String getSonStr(int n,String s){
        char a[]=new char[n];
        for(int i=0;i<n;i++) {
            a[i]=s.charAt(i);
        }
        String str=new String(a);
        return str;
    }
    public boolean isSonString(String s1,String s2){
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1%len2 !=0) return false;
        int i=0,j=0;
        for(;i<len1;){
            if(s1.charAt(i) != s2.charAt(j)){
                return false;
            }
            i++;j++;
            if(j == len2){
                j = 0;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        String str = "abcabcabcabc";
        repeatedSubstringPattern rp = new repeatedSubstringPattern();
        System.out.println(rp.repeatedSubstringPattern1(str));
    }
}
